\section{Algoritmo Exacto}

\subsection{Introducci'on}
El algoritmo exacto es un algoritmo de fuerza bruta, el cual va calculando todas las posibles soluciones con ciertas restricciones hasta que, o bien recorre todas las posibles soluciones hasta hallar una combinaci'on de variables que satisfaga a todas las cl'ausulas o, en el peor caso, recorre todas las posibles soluciones y devuelve la mejor encontrada. \\

\subsection{Soluci'on}

La soluci'on se basa en lo siguiente, dado $V$ vector con todas las variables en $0$, evaluamos cuantas cl'ausulas hace verdaderas y sumamos $1$ como si $V$ fuese un n'umero binario de largo $v$. Entonces si tenemos $V = \{0,0,\ldots,0\}$ y sumamos $1$ como si fuese un numero binario nos queda $V = \{1,0,\ldots,0\}$, si repetimos el proceso nos queda $V = \{0,1,\ldots,0\}$, etc. De esta forma nos podemos generar todas las posibles combinaciones de variables y sus negaciones.

Analizando la entrada del problema vimos que recorriendo todas las cl'ausulas de un caso de prueba podemos fijar ciertas variables seg'un el siguiente criterio. Sea $V_i$ variable que solamente aparece como negada o solamente como no negada, podemos fijar esta en nuestro $V$ ya que probar con el valor opuesto al que aparece en las cl'ausulas no satisfaceria ninguna cl'ausula en las que aparece. 

Adaptando la forma de generar todas las posibles soluciones con esta restricci'on de dejar algunas variables fijas, la suma binaria sobre el vector se modifica de la siguiente forma. Ejemplo: Sea $V_2$ la variable que queda fija en $1$ tenemos a $V = \{0,1,0,\ldots,0\}$, entonces sumamos $1$ y nos queda $V = \{1,1,0,\ldots,0\}$, volvemos a sumar, pero como $V_2$ estaba fijo, salteamos a $V_2$ y obtenemos $V = \{0,1,1,\ldots,0\}$ sin alterar el valor de $V_2$.

Por cada soluci'on que generamos nos fijamos cuantas cl'ausulas satisfacemos, si la cantidad de cl'ausulas satisfechas es igual a la cantidad de cl'ausulas del caso de prueba: terminamos, sino nos vamos quedando con la soluci'on que m'as cl'ausulas sastisface hasta recorrer todas las soluciones y devolvemos la mejor encontrada. 

\subsection{Pseudoc'odigo}

\newcommand{\exacto}{\ensuremath{\mbox{\sc exacto}}}
	\begin{algorithm}[H]
		\caption{\exacto(CasoDePrueba casoDePrueba)}\label{alg:exacto}
			\medskip
			\begin{algorithmic}[1]
			\STATE $V \leftarrow \{0_1,0_2,\ldots,0_v\}$
			\STATE $MejorVEncontrado \leftarrow \{0_1,0_2,\ldots,0_v\}$
			\STATE $VectorFijos \leftarrow \{0_1,0_2,\ldots,0_v\}$
			\STATE $VectorFijos \leftarrow$ encontrarVariablesFijas($V$, $casoDePrueba$)
			
			\FOR {(i desde $1$ hasta $2^{v - CantVariablesFijadas} + 1$)} 
				  
				  \IF {($V$ satisface Todas las Cl'ausulas del $casoDePrueba$)}
							\STATE devolver $V$
				  \ENDIF
				  
				  \IF {$V$ satisface m'as cl'ausulas que $MejorVEncontrado$ en el $casoDePrueba$}
							\STATE $MejorVEncontrado \leftarrow V$
				  \ENDIF
				  
				  \STATE $V \leftarrow$ sumaBinaria($V$, $VectorFijos$)
			
			\ENDFOR	
			
			\STATE devolver $MejorVEncontrado$
			
			\end{algorithmic}
	\end{algorithm}

\subsubsection{Explicaci'on}

Inicialmente llamamos a la funci'on \textbf{encontrarVariablesFijas} que se encarga de recorrer todas las cl'ausulas del $casoDePrueba$ y encuentra aquellas variables que solo aparecen negadas o solo aparecen no negadas y actualiza el valor en las posici'ones $i$-'esimas, correspondientes a las variables encontradas, en el vector $VectorFijos$ en $1$, que indica que la variable $V_i$ est'a marcada como variable fija, y actualiza el valor en $V_i$ seg'un lo encontrado.

Despues recorremos todas las posibles combinaciones que nos quedan las cuales estan dadas por $2^{v - CantVariablesFijadas}$ ya que cada variable no fijada se puede negar o no negar. Cada vez que generamos una posible soluci'on chequeamos la cantidad de cl'ausulas satisfechas y nos vamos quedando con la mejor hasta que satisfacemos todas las cl'ausulas o bien recorrimos todo las posibilidades y devolvemos la mejor encontrada.

La funci'on sumaBinaria se encarga de sumar $1$ sobre $V$ respetando las variables fijas dadas en $VectorFijos$.

\subsection{An'alisis de Complejidad}

El an'alisis de la complejidad es relativamente sencillo, ya que al tener $V$ vector de tama'no $v$, suponiendo que no tenemos variables fijas y que los posibles valores del vector son solamente ${0,1}$ la cantidad de combinaciones que podemos encontrar es $2^{v}$. 
La funci'on sumaBinaria tarda en el peor caso $v$.
Adicionalmente tenemos que calcular el costo de chequear la cantidad de cl'ausulas satisfechas por la soluci'on. Esta operaci'on lo resolvemos en $c.v$ lo que nos da una complejidad de O($2^{v}(c.v+v)$) que es O($2^{v}(c.v+v)$).

\subsection{Experimentos y Gr'aficos}
\subsubsection{De los casos de prueba}
Para generar cada caso de prueba se tomaron en cuenta las siguientes variables:

\begin{itemize}
	\item Cantidad de cl'asulas
	\item Cantidad de variables
	\item Cantidad de variables por cl'asula 
	\item Cantidad de casos de prueba
\end{itemize}

Decidimos contar la cantidad de operaciones para medir emp'iricamente la complejidad.

Un peor caso para este algoritmo, ser'ia aquel que no fijara variables de antemano, entonces deber'ia recorrer todas las soluciones posibles.

Otro peor caso ser'ia contemplar el caso anterior y que no se pudieran hacer verdaderas todas las cl'asulas, entonces deber'ia recorrer todas las soluciones posibles pues la mejor soluci'on ser'ia incierta.

La \textit{Cantidad de variables por cl'asula} son tomadas al azar entre 1 y la \textit{Cantidad de variables}. Para conseguir este n'umero usamos un m'etodo de la plataforma Java 2, versi'on 6, que nos genera un valor entre 0 y 1 de forma uniforme, a partir de este valor conseguimos. Seg'un su javadoc: \textbf{Returned values are chosen pseudorandomly with (approximately) uniform distribution}, los valores provienen de una distribuci'on aproximadamente uniforme.

La \textit{Cantidad de variables}, \textit{Cantidad de cl'ausulas} y \textit{Cantidad de casos de prueba} son fijadas de antemano para generar los casos de prueba y sus diferentes variantes.

Las escalas elegidas para estos gr'aficos en general son logar'itmicas para el eje que cuenta operaciones para apreciar la diferencia entre las funciones graficadas. Muchos casos de prueba resultaron poco informativos porque la diferencia entre la complejidad te'orica y la calculada emp'iricamente era demasiado grande, obteniendo valores muy alejados y apreciando solo una funci'on y no la comparaci'on entre ambas.

La complejidad te'orica, en los gr'aficos, esta multiplicada por una constante.

La cantidad de varibles no puede ser tan grande porque el algoritmo demora mucho tiempo, en general las pruebas contienen solo hasta 14 variables. No as'i la cantidad de cl'asulas. Es importante destacar que la variable principal es la cantidad de variables, porque la complejidad del algoritmo, que es exponencial, depende de esta.


\subsubsection{Gr'aficos complejidad te'orica vs Complejidad medida en la pr'actica}
\begin{center}
	\includegraphics[width=0.9999\textwidth]{dibujos/Exacto/Complejidad/Exact_150_clas_14_vars_5_Rand_5_Casos_escala_log.png}
\end{center}
\begin{itemize}
	\item Cantidad de cl'asulas: 150
	\item Cantidad de variables: 1 a 14
	\item Cantidad de casos de prueba: 5
\end{itemize}

Se puede ver claramente como la tendencia de la funci'on de la complejidad pr'actica es imitar a la te'orica, salvo casos aislados. Estos casos aislados se mantienen por debajo de la complejidad te'orica y son casos en los que se fijaron muchas variables de antemano. Se corrieron 5 casos por variable, y sin embargo la mayor'ia obtiene los mismos resultados, salvo los casos aislados que se pudieron llegar a acotar la cantidad de soluciones analizadas. 

Algo importante es ver que cuando $v > 8$ comienzan a aparecer casos en los cuales fijamos variables ya que al haber mayor cantidad de variables, la probabilidad de que alguna quede fija aumenta.

\newpage
\begin{center}
	\includegraphics[width=0.9999\textwidth]{dibujos/Exacto/Complejidad/Exact_250_clas_9_vars_5_Rand_25_Casos_escala_log.png}
\end{center}
\begin{itemize}
	\item Cantidad de cl'asulas: 250
	\item Cantidad de variables: 1 a 9
	\item Cantidad de casos de prueba: 25
\end{itemize}
Al igual que en el caso anterior, la funci'on de la complejidad pr'actica imita a la te'orica. Las variaciones son m'as notorias, a partir de 6 variables, por la cantidad de casos de prueba analizados.

\newpage
\begin{center}
	\includegraphics[width=0.9999\textwidth]{dibujos/Exacto/Complejidad/Exact_1000_clas_9_vars_1_Rand_25_Casos_escala_log.png}
\end{center}
\begin{itemize}
	\item Cantidad de cl'asulas: 1000
	\item Cantidad de variables: 1 a 9
	\item Cantidad de casos de prueba: 25
\end{itemize}
Para este gr'afico intentamos aumentar la cantidad de cl'asulas para ver como se comportaba el algoritmo. No hay variaci'on con los casos anteriores, aumenta un poco la cantidad de operaciones pero la cantidad de casos que se aleja de la complejidad te'orica, casos que termina antes de analizar todas las soluciones, aparecen reci'en a partir de 8 variables. 


\newpage
\begin{center}
	\includegraphics[width=0.9999\textwidth]{dibujos/Exacto/Complejidad/Exact_150_clas_14_vars_5_Rand_5_Casos_escala_normal.png}
\end{center}
\begin{itemize}
	\item Cantidad de cl'asulas: 150
	\item Cantidad de variables: 1 a 14
	\item Cantidad de casos de prueba: 5
\end{itemize}
Este caso ilustra un poco mejor el comportamiento exponencial en la cantidad de variables. Sin embargo la complejidad pr'actica se aleja bastante de la te'orica. Se puede ver, al no aplicar escala logar'itmica la diferencia exponencial, del orden de $10^8$ entre la complejidad pr'actica y te'orica cuando se encuentra la soluci'on r'apidamente.

\newpage
\subsection{Conclusiones}
\subsubsection{En cuanto a la complejidad del algoritmo}

Es importante ver la diferencia que hay entre encontrar una soluci'on r'apidamente y no encontrarla, hay casos, por ejemplo, para 14 variables en donde la diferencia es del orden de $10^8$ operaciones($2^{14}$ x 150 x 14 x $K$, con $K$ constante). Tambi'en es importante que para casos en los que se tiene que recorrer todas las posibles soluciones la complejidad pr'actica se mantiene por debajo de la complejidad te'orica, la diferencia para estos casos entre las funciones est'a dada por la constante que multiplica la complejidad te'orica.

\subsubsection{En cuanto a la soluci'on propuesta}
Si bien no es la mejor soluci'on, es clara y simple, encuentra siempre la combinaci'on de variables que maximiza las cl'ausulas. No es la mejor soluci'on porque de la forma que construimos nuestra posible soluci'on no pudimos encontrar podas f'aciles de implementar. Tambi'en vemos lo importante de implementar heur'isticas, con mas de 20 variables el algoritmo es impracticable.

Una posible mejora hubiera estado centrada en el chequear cl'asulas satisfechas cuando construimos una posible soluci'on, nuestra complejidad para dicha operaci'on es $c$ x $v$, creemos que lo podr'iamos haber implementado con una complejidad de O($c$), pero debido al escaso tiempo no pudimos realizarla. Nos centramos m'as en las pruebas de las heur'isticas.

